﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 算法
{
    /// <summary>
    /// 对于一个图的描述
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Graph<T>
    {
        /// <summary>
        /// 结点的编号对应的结点的字典
        /// </summary>
        public Dictionary<int, Node> nodes;
        /// <summary>
        /// 边的集合,由于边会存在重复写入的情况,所以用HashSet存储
        /// </summary>
        public HashSet<Edge> edges;

        public bool IsHasRing => _IsHasRing();

        public int Connectivity => GetConnectivity();

        public Graph()
        {
            this.nodes = new();
            this.edges = new();
        }

        /// <summary>
        /// 对图的一个结点进行广度优先遍历
        /// </summary>
        /// <param name="node"></param>
        public static void BreadthFirstTraversal(Node node, Action<Node> action)
        {
            if (node == null)
            {
                return;
            }
            Queue<Node> queue = new();
            HashSet<Node> set = new();
            queue.Enqueue(node);
            set.Add(node);
            while (queue.Count != 0)
            {
                Node cur = queue.Dequeue();
                action(cur);
                foreach (Node item in cur.nexts)
                {
                    if (!set.Contains(item))
                    {
                        queue.Enqueue(item);
                        set.Add(item);
                    }
                }
            }
        }

        /// <summary>
        /// 对一个图的结点进行深度优先遍历
        /// </summary>
        /// <param name="node"></param>
        public static void DepthFirstTraversal(Node node, Action<Node> action)
        {
            if (node == null)
            {
                return;
            }
            Stack<Node> stack = new();
            HashSet<Node> set = new();
            stack.Push(node);
            set.Add(node);
            action(node);
            while (stack.Count != 0)
            {
                Node cur = stack.Pop();
                foreach (Node item in cur.nexts)
                {
                    if (!set.Contains(item))
                    {
                        stack.Push(cur);
                        stack.Push(item);
                        set.Add(item);
                        action(item);
                        break;
                    }
                }
            }
        }

        /// <summary>
        /// 获取图的连通度
        /// </summary>
        /// <returns></returns>
        private int GetConnectivity()
        {
            UnionSet<Node> unionSet = new(nodes.Values);
            PriorityQueue<Edge, int> priorityQueue = new();
            foreach (Edge item in edges)
            {
                priorityQueue.Enqueue(item, item.weight);
            }
            while (priorityQueue.Count != 0)
            {
                Edge edge = priorityQueue.Dequeue();
                if (!unionSet.InSameSet(edge.from, edge.to))
                {
                    unionSet.Union(edge.from, edge.to);
                }
            }
            return unionSet.GetNumberOfSets();
        }

        /// <summary>
        /// 对一张图进行拓扑排序
        /// </summary>
        /// <param name="graph"></param>
        /// <returns></returns>
        public List<Node> SortedTopology()
        {
            if (IsHasRing)
            {
                throw new Exception("此图有环,无法进行拓扑排序!");
            }
            // 结点对应的结点剩余入度的字典
            Dictionary<Node, int> inMap = new(nodes.Count);
            //剩余入度为0的点才能进入这个队列
            Queue<Node> zeroInQueue = new(nodes.Count / 2);
            foreach (Node item in nodes.Values)
            {
                inMap.Add(item, item.indegree);
                if (item.indegree == 0)
                {
                    zeroInQueue.Enqueue(item);
                }
            }
            //此次拓扑排序的结果
            List<Node> result = new(nodes.Count);
            while (zeroInQueue.Count != 0)
            {
                Node cur = zeroInQueue.Dequeue();
                result.Add(cur);
                foreach (Node item in cur.nexts)
                {
                    inMap[item]--;
                    if (inMap[item] == 0)
                    {
                        zeroInQueue.Enqueue(item);
                    }
                }
            }
            return result;
        }

        /// <summary>
        /// 克鲁斯卡尔算法求本图的最小生成树结果
        /// </summary>
        /// <returns></returns>
        public HashSet<Edge> KruskalMinimumSpanningTree()
        {
            UnionSet<Node> unionSet = new(nodes.Values);
            PriorityQueue<Edge, int> priorityQueue = new();
            HashSet<Edge> result = new();
            foreach (Edge item in edges)
            {
                priorityQueue.Enqueue(item, item.weight);
            }
            while (priorityQueue.Count != 0)
            {
                Edge edge = priorityQueue.Dequeue();
                if (!unionSet.InSameSet(edge.from, edge.to))
                {
                    result.Add(edge);
                    unionSet.Union(edge.from, edge.to);
                }
            }
            return result;
        }

        /// <summary>
        /// 普里姆算法求本图的最小生成树结果
        /// </summary>
        /// <returns></returns>
        public List<HashSet<Edge>> PrimMinimumSpanningTree()
        {
            PriorityQueue<Edge, int> priorityQueue = new();
            HashSet<Node> nodeSet = new();
            HashSet<Edge> edgeSet = new();
            List<HashSet<Edge>> result = new();
            int count = 0;
            foreach (Node node in nodes.Values)
            {
                if (!nodeSet.Contains(node))
                {
                    result.Add(new());
                    nodeSet.Add(node);
                    foreach (Edge edge in node.edges)
                    {
                        if (!edgeSet.Contains(edge))
                        {
                            edgeSet.Add(edge);
                            priorityQueue.Enqueue(edge, edge.weight);
                        }
                    }
                    while (priorityQueue.Count != 0)
                    {
                        Edge edge = priorityQueue.Dequeue();
                        Node toNode = edge.to;
                        if (!nodeSet.Contains(toNode))
                        {
                            nodeSet.Add(toNode);
                            result[count].Add(edge);
                            foreach (Edge nextEdge in toNode.edges)
                            {
                                if (!edgeSet.Contains(nextEdge))
                                {
                                    edgeSet.Add(nextEdge);
                                    priorityQueue.Enqueue(nextEdge, nextEdge.weight);
                                }
                            }
                        }
                    }
                    count++;
                }
            }
            return result;
        }

        /// <summary>
        /// 迪杰斯特拉算法求最短距离
        /// </summary>
        /// <param name="from"></param>
        /// <returns></returns>
        public static Dictionary<Node, int> Dijkstra(Node from)
        {
            Dictionary<Node, int> distanceMap = new Dictionary<Node, int>();
            distanceMap.Add(from, 0);
            HashSet<Node> selectedNodes = new HashSet<Node>();
            Node minNode = GetMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
            while (minNode != null)
            {
                int distance = distanceMap[minNode];
                foreach (Edge edge in minNode.edges)
                {
                    Node toNode = edge.to;
                    if (!distanceMap.ContainsKey(toNode))
                    {
                        distanceMap.Add(toNode, distance + edge.weight);
                    }
                    else
                    {
                        distanceMap[toNode] = Math.Min(distanceMap[toNode], distance + edge.weight);
                    }
                }
                selectedNodes.Add(minNode);
                minNode = GetMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
            }
            return distanceMap;
        }

        private static Node GetMinDistanceAndUnselectedNode(Dictionary<Node, int> distanceMap, HashSet<Node> selectedNodes)
        {
            int dis = int.MaxValue;
            Node minNode = null;
            foreach (var item in from map in distanceMap where (!selectedNodes.Contains(map.Key) && dis >= map.Value) select map)
            {
                minNode = item.Key;
                dis = item.Value;
            }
            return minNode;
        }

        private bool _IsHasRing()
        {
            UnionSet<Node> unionSet = new(nodes.Values);
            foreach (Edge edge in edges)
            {
                if (!unionSet.InSameSet(edge.from, edge.to))
                {
                    unionSet.Union(edge.from, edge.to);
                }
                else
                {
                    return true;
                }
            }
            return false;
        }

        /// <summary>
        /// 对于一个图点的描述
        /// </summary>
        public class Node
        {
            /// <summary>
            /// 此点代表的数值
            /// </summary>
            public T value;
            /// <summary>
            /// 代表了此点的id编号
            /// </summary>
            public int no;
            /// <summary>
            /// 入度是多少
            /// </summary>
            public int indegree;
            /// <summary>
            /// 入度是多少
            /// </summary>
            public int ourtdegree;
            /// <summary>
            /// 此结点直接连接的下一个结点
            /// </summary>
            public List<Node> nexts;
            /// <summary>
            /// 以此结点为初始结点的边
            /// </summary>
            public List<Edge> edges;

            public Node(int no)
            {
                this.value = default;
                this.no = no;
                indegree = 0;
                ourtdegree = 0;
                nexts = new List<Node>();
                edges = new List<Edge>();
            }

            public Node(T value, int no)
            {
                this.value = value;
                this.no = no;
                indegree = 0;
                ourtdegree = 0;
                nexts = new List<Node>();
                edges = new List<Edge>();
            }
        }

        /// <summary>
        /// 对于一个图边的描述
        /// </summary>
        public class Edge
        {
            /// <summary>
            /// 边的权重
            /// </summary>
            public int weight;
            /// <summary>
            /// 此边从哪个结点来的
            /// </summary>
            public Node from;
            /// <summary>
            /// 此边到哪个结点
            /// </summary>
            public Node to;

            public Edge(int weight, Node from, Node to)
            {
                this.weight = weight;
                this.from = from;
                this.to = to;
            }
        }
    }

}
